/**
 * 冒泡排序
 * 
 * 基本思想:
 * 把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。
 * 接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。
 * 除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。
 * 
 * 具体步骤：
 * 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 * 3.针对所有的元素重复以上的步骤，除了最后一个。
 * 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 * 
 * 
 * 最好时间复杂度：O(N)
 * 最坏时间复杂度：O(N^2)
 * 平均时间复杂度：O(N^2)
 * 空间复杂度：O(1)
 * 
 * 
 * 稳定排序:是
 * 原地排序:是
*/

#include "../../include/common.h"

// 升序
void BubbleSort(ElementType *arr, int len) {
    int i, j;
    for(i=0; i<len-1; i++)
        for(j=0; j<len-1-i; j++)
            if(arr[j] > arr[j+1]){
                Swap(arr, j, j+1);
            }
}


/**
 * 改进：
 * 1.一般的冒泡排序方法有可能会在已经排好序的情况下继续比较，
 *  改进的冒泡排序，设置了一个哨兵flag，如果一次for循环没有进行交换，则元素已经排好序，由哨兵控制退出循环。
 * 
 * 2.有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 。
 *  实际上，数列真正的有序区可能会大于这个长度，比如仅仅第二轮，后面5个元素实际都已经属于有序区。
 *  因此后面的许多次元素比较是没有意义的。 如何避免这种情况呢？
 *  我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

*/